using NUnit.Framework;

namespace Solver
{
	/// <summary>
	/// Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?
	/// </summary>
	public class Problem015 : SelfChecker, IProblem
	{
		public int Id
		{
			get { return 15; }
		}

		public string Solve()
		{
			return Solve(20).ToString();
		}

		[Test]
		public override void Check()
		{
			Assert.AreEqual(2, Solve(1));
			Assert.AreEqual(6, Solve(2));
			Assert.AreEqual(20, Solve(3));
			Assert.AreEqual(137846528820, Solve(20));
		}

		// This is Pascal's Triagle! And the answer is actually C(2n, n)
		private static long Solve(int param)
		{
			var d = new long[param + 1, param + 1];
			d[0, 0] = 1;
			for (int n = 1; n <= param; n++)
			{
				d[n, 0] = 1;
				for (int k = 1; k < n; k++)
					d[n, k] = d[n - 1, k] + d[n, k - 1];
				d[n, n] = 2 * d[n, n - 1];
			}
			return d[param, param];
		}
	}
}